package leetcode_day._2021._202109._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/17 15:55
 * 有效的数独
 * 算法：数组
 * 直接上三个数组
 * 一个表示列，一个表示行，一个表示宫格
 * 9 * 9 宫格分成 9 个 3 * 3 宫格
 * 使用 block[9][9] 表示每块中 1 ~ 9 数字是否存在
 * (i / 3, j / 3) 按照 (i, j) 定位到 3 * 3 宫格的位置
 * 比如 board[1][2], 它所在的 3 * 3 宫格的位置为 (0, 0), board[6][3] --> (2, 1)
 */
public class _17_36 {
    public static void main(String[] args) {
        final char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {
                '.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {
                '4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {
                '.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {
                '.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        System.out.println(new _17_36().isValidSudoku(board));
    }

    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][] block = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int n = c - '0' - 1;
                    int ii = i / 3 * 3, jj = j / 3;
                    if (row[i][n] || col[j][n] || block[ii + jj][n]) return false;
                    row[i][n] = true;
                    col[j][n] = true;
                    block[ii + jj][n] = true;
                }
            }
        }
        return true;
    }

}
